LeetCode 110、平衡二叉树

一、题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 平衡二叉树（ LeetCode 110 ）:https://leetcode-cn.com/problems/balanced-binary-tree
class Solution {
    public boolean isBalanced(TreeNode root) {
         // 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
        return recur(root) != -1;
    }

    private int recur(TreeNode curNode) {
        
        // 递归终止条件
        // 如果当前节点 curNode 为空，那么高度就是 0
        if (curNode == null) return 0;

        // 递归的计算当前节点 curNode 的左子树高度
        int left = recur(curNode.left);

        // 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(left == -1) return -1;

        // 递归的计算当前节点 curNode 的右子树高度
        int right = recur(curNode.right);

        // 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(right == -1) return -1;

        // 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
        // 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
        // 因此计算一下当前节点 curNode 是否是平衡二叉树
        // 即计算 curNode 的左子树高度与右子树高度差
        // 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
        // 即节点 curNode 的左右子树中最大高度加 1 
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 平衡二叉树（ LeetCode 110 ）:https://leetcode-cn.com/problems/balanced-binary-tree
class Solution {
public:
    bool isBalanced(TreeNode* root) {
         // 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
        return recur(root) != -1;
    }
private:
    int recur(TreeNode* curNode) {
        
        // 递归终止条件
        // 如果当前节点 curNode 为空，那么高度就是 0
        if (curNode == NULL) return 0;

        // 递归的计算当前节点 curNode 的左子树高度
        int left = recur(curNode->left);

        // 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(left == -1) return -1;

        // 递归的计算当前节点 curNode 的右子树高度
        int right = recur(curNode->right);

        // 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(right == -1) return -1;

        // 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
        // 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
        // 因此计算一下当前节点 curNode 是否是平衡二叉树
        // 即计算 curNode 的左子树高度与右子树高度差
        // 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
        // 即节点 curNode 的左右子树中最大高度加 1 
        return abs(left - right) < 2 ? max(left, right) + 1 : -1;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 平衡二叉树（ LeetCode 110 ）:https://leetcode-cn.com/problems/balanced-binary-tree
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
         # 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
        return self.recur(root) != -1
    

    def recur(self, curNode: TreeNode):
        
        # 递归终止条件
        # 如果当前节点 curNode 为空，那么高度就是 0
        if not curNode : return 0

        # 递归的计算当前节点 curNode 的左子树高度
        left = self.recur(curNode.left)

        # 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        # 提前终止了后续的判断
        if left == -1 : return -1

        # 递归的计算当前节点 curNode 的右子树高度
        right = self.recur(curNode.right)

        # 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        # 提前终止了后续的判断
        if right == -1 : return -1

        # 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
        # 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
        # 因此计算一下当前节点 curNode 是否是平衡二叉树
        # 即计算 curNode 的左子树高度与右子树高度差
        # 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
        # 即节点 curNode 的左右子树中最大高度加 1 
        return max(left, right) + 1 if abs(left - right) < 2 else -1